# dfs
# class Solution(object):
#     def assignBikes(self, workers, bikes):
#         """
#         :type workers: List[List[int]]
#         :type bikes: List[List[int]]
#         :rtype: int
#         """
#         n = len(workers)
#         m = len(bikes)
#         b_set = {i for i in range(m)}
#
#         def cal(i, j):
#             return abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1])
#
#         def search(i, b_set):
#             min_num = float('inf')
#             if i == n:
#                 return 0
#             else:
#                 for item in b_set:
#                     new_b_set = b_set.copy()
#                     new_b_set.remove(item)
#                     min_num = min(min_num, cal(i, item) + search(i + 1, new_b_set))
#             return min_num
#         return search(0, b_set)

class Solution(object):
    def assignBikes(self, workers, bikes):
        """
        :type workers: List[List[int]]
        :type bikes: List[List[int]]
        :rtype: int
        """
        m = len(workers)
        n = len(bikes)

        def ms(i, j):
            return abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1])

        grid = [[0 for _ in range(n)] for _ in range(m)]
        for i in range(m):
            for j in range(n):
                grid[i][j] = ms(i, j)

        x_score = [min(grid[i]) for i in range(m)]
        y_score = [0] * n
        x_flag = [-1] * m
        y_flag = [-1] * n
        needed = [float('inf')] * n
        def find(i):
            used_x[i] = 1
            for j in range(n):
                if not used[j]:
                    diff = grid[i][j] - x_score[i] - y_score[j]
                    if diff == 0:
                        used[j] = 1
                        if y_flag[j] == -1 or find(y_flag[j]):
                            x_flag[i] = j
                            y_flag[j] = i
                            return True
                    else:
                        needed[j] = min(diff, needed[j])
            return False

        for i in range(m):
            used = [0] * n
            used_x = [0] * m
            while not find(i):
                d = float('inf')
                for j in range(n):
                    if not used[j]:
                        d = min(d, needed[j])
                for j in range(m):
                    if used_x[j]:
                        x_score[j] += d
                for j in range(n):
                    if used[j]:
                        y_score[j] -= d
                used = [0] * n
                used_x = [0] * m
        total = 0
        for i in range(m):
            total += grid[i][x_flag[i]]
        return total


data = Solution()
workers = [[0, 0], [1, 1], [2, 0]]
bikes = [[1, 0], [2, 2], [2, 1]]
print(data.assignBikes(workers, bikes))
workers = [[0, 0], [2, 1]]
bikes = [[1, 2], [3, 3]]
print(data.assignBikes(workers, bikes))
workers = [[0, 0], [1, 0], [2, 0], [3, 0], [4, 0]]
bikes = [[0, 999], [1, 999], [2, 999], [3, 999], [4, 999]]
print(data.assignBikes(workers, bikes))
workers = [[0, 0], [1, 0], [2, 0], [3, 0], [4, 0], [5, 0], [6, 0], [7, 0], [8, 0], [9, 0]]
bikes = [[0, 999], [1, 999], [2, 999], [3, 999], [4, 999], [5, 999], [6, 999], [7, 999], [8, 999], [9, 999]]
print(data.assignBikes(workers, bikes))
workers = [[239, 904], [191, 103], [260, 117], [86, 78], [747, 62]]
bikes = [[660, 8], [431, 772], [78, 576], [894, 481], [451, 730], [155, 28]]
print(data.assignBikes(workers, bikes))
